
import java.util.*;

public class dome {
    static Map<Integer,List<TreeNode>> map = new HashMap<>();
    public static void main(String[] args) {
        //System.out.println(allPossibleFBT(7));
        Deque<Integer> deque = new ArrayDeque<>();
        Stack<Integer> stack = new Stack<>();
        for(int i = 1;i<=10;i++){
            deque.push(i);
            stack.push(i);
        }
        System.out.println("deque.pop="+deque.removeLast());
        System.out.println("stack.pop="+stack.pop());
        System.out.println(deque);
        System.out.println(stack);
    }
    //找出所有的二叉排序树
    public static List<TreeNode> getALL(int start,int ed){
        List<TreeNode> list = new ArrayList<>();
        if(start>ed){
            list.add(null);
            return list;
        }
        for(int i =start;i<ed;i++){
            for (TreeNode left : getALL(start, i - 1)) {
                for (TreeNode right : getALL(i + 1, ed)) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    list.add(root);
                }
            }
        }
        return list;
    }
//找出所有的满二叉树
    public static List<TreeNode> allPossibleFBT(int n){
        if(!map.containsKey(n)){
            List<TreeNode> list = new ArrayList<>();
            if(n==1){
                list.add(new TreeNode(0));
            }else if(n%2==1){
                for(int i =0;i<n-1;i++){
                    int j = n-i-1;
                    for (TreeNode left : allPossibleFBT(i)) {
                        for (TreeNode right : allPossibleFBT(j)) {
                            TreeNode root = new TreeNode(0);
                            root.left = left;
                            root.right = right;
                            list.add(root);
                        }
                    }
                }
            }
            map.put(n,list);
        }
        return map.get(n);
    }
}

